Дек
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть шарики, пронумерованные от $$$1$$$ до $$$n$$$. Также поступают $$$q$$$ запросов:

На запросы $$$1$$$-го типа вы тратите $$$1$$$ действие, а на запросы $$$2$$$-го типа - $$$2k + 1$$$ действий, где $$$k$$$ - количество шариков, которые лежат ниже удаляемого (то есть вы сначала достаете $$$k$$$ шариков, потом удаляете нижний, потом кладете достанные $$$k$$$ шариков обратно в том же порядке).

Посчитайте, какое минимальное количество действий вы можете потратить.

Входные данные

Первая строка содержит числа $$$n$$$ и $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^5$$$) - максимальный номер шарика и количество запросов. Далее следуют $$$q$$$ строк в формате:

Гарантируется, что никакой шарик не добавляется 2 раза, а также, что если есть запрос удаления шарика $$$x$$$, то он присутствует в деке в данный момент.

Выходные данные

Выведите единственное число - минимальное количество операций, которое вы можете потратить на запросы.

Система оценки

Подзадача 1. $$$q \le 20$$$ - набирает не менее 15% баллов.

Подзадача 2. В любой момент времени в деке хранится не больше 6 элементов, $$$q \le 1000$$$ - набирает не менее 30% баллов.

Подзадача 3. В любой момент времени в деке хранится не больше 10 элементов, $$$q \le 1000$$$ - набирает не менее 40% баллов.

Подзадача 4. $$$q \cdot n \le 10^6$$$ - набирает не менее 65% баллов.

Подзадача 5. $$$q \le 5000$$$ - набирает не менее 70% баллов.

Подзадачи вложенны друг в друга, т.е. если вы сдали какую-то из подзадач, вы автоматически сдали и все подзадачи до неё.

Примеры

Входные данные
2 4
add 1
del 1
add 2
del 2
Выходные данные
4
Входные данные
8 6
add 5
add 8
del 5
add 1
add 4
del 1
Выходные данные
6

Примечание

В тесте 1 независимо от того, как вы добавите шарики, вы потратите 4 действия (на удаление и на добавление каждого из шариков).

В тесте 2 вам необходимо добавить шарик 5 вниз, шарик 8 вверх, шарик 1 вниз, шарик 4 вверх, тогда вы потратите ровно 6 действий.